#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

class Solution2 {
    public:
        int maxArea(vector<int> &height) {
            int size = height.size();
            int best = 0;
            int i = 0, j = size -1;
            int start, end;
            while ( i < j) {
                int vol = (j-i) * min(height[i], height[j]);
                if (vol > best) {
                    start = i;
                    end = j;
                    best = vol;
                }
                if (height[i] <= height[j]) {
                    while(i + 1 < size && height[i+1] < height[i]) i++;
                    i++;
                } else {
                    while (j > 0 && height[j] > height[j-1]) j--;
                    j--;
                }
            }
            //cout << start << " " << end << endl;
            return best;
        }
};

class Solution {
    public:
        int maxArea(vector<int> &height) {
            int best = 0;
            int i = 0, j = height.size() -1;
            while ( i < j) {
                int vol = (j-i) * min(height[i], height[j]);
		best = max(best, vol);
                if (height[i] <= height[j]) {
                    i++;
                } else {
                    j--;
                }
            }
            return best;
        }
};

//test in the online judge and pass all the test
int main(int argc, char **argv)
{
    Solution mySolution;
    vector<int> input;
    int test[] = {4,2,1,5,4,3,2};
    for (int i = 0; i < sizeof(test)/sizeof(int); i++) {
        input.push_back(test[i]);
    }
    int result = mySolution.maxArea(input);
    cout << "Result is" << result << endl;
}
